package tree;

/**
 * @Author wangtengyu
 * @Create 2018-09-12-8:43
 * <p>
 * 查看A树中是否包含b树的结构 思路 1.节点值不相同 去左子树找，左子树不相同，再去右子树找。
 * <p>
 * 2.节点值相同后，再比较接下来是否相同 比较的终结是tree2到头了 两者都为null，包含 tree1不为null，tree为null 包含 tree1为null，tree不为null 不包含
 * 两者都不为null，判断值是否相同
 */
public class IncludeTree {


  public boolean inCludeTree(TreeNode tree1, TreeNode tree2) {
    boolean result = false;

    if (tree1 == null || tree2 == null) {
      return result;
    }

    if (tree1.getValue() == tree2.getValue()) {
      result = isTree1HaveTree2(tree1, tree2);
    }
    if (!result) {
      result = inCludeTree(tree1.getLeft(), tree2);
    }
    if (!result) {
      result = inCludeTree(tree1.getRight(), tree2);
    }
    return result;
  }

  /**
   * 递归的出口条件可能是这一次的，也可能是下一次的。
   */
  private boolean isTree1HaveTree2(TreeNode tree1, TreeNode tree2) {
    //两者都为null，或者只有tree2为null
    if (tree2 == null) {
      return true;
    }
    //tree1为null且tree2不为null，肯定是不包含的
    if (tree1 == null) {
      return false;
    }

    //两者都不为null的情况，判断是否相等  相等的话还要继续往后判断，不能返回true；
    if (tree1.getValue() != tree2.getValue()) {
      return false;
    }

    return (isTree1HaveTree2(tree1.getLeft(), tree2.getLeft()) && isTree1HaveTree2(tree1.getRight(),
        tree2.getRight()));
  }


  public static void main(String[] args) {
    SimpleTreeCreator creator = new SimpleTreeCreator();
    IncludeTree includeTree = new IncludeTree();
    TreeNode tree1 = creator.createSampleTree();
    TreeNode tree2 = new TreeNode('B');
    tree2.setLeft(new TreeNode('D'));
    tree2.setRight(new TreeNode('E'));
    tree2.getRight().setRight(new TreeNode('E'));
    boolean isInClude = includeTree.inCludeTree(tree1, tree2);
    System.out.println(isInClude);
    if (isInClude) {
      System.out.println("tree1包含tree2");
    } else {
      System.out.println("tree1不包含tree2");
    }
  }
}
